package com.sinaapp.gavinzhang.jianzhioffer;

/**
 * 查找一个有序数组转置后的最小值
 * Created by gavin on 15-9-3.
 */
public class FindSmall {
    public static void main(String[] args)
    {
        //int[] tmp = {4,5,1,2,3};
        //int[] tmp = {3,4,5,1,2};
        //int[] tmp = {2,2,2,2,1,2};
        //int[] tmp = {1,1,1,0,1};
        //int[] tmp = {1,2,2,2,2,2};
        int[] tmp = {2,2,1,2,2,2};
        //int[] tmp = {1,0,1,1,1};
        System.out.println(minNumberInRotateArray(tmp));
    }

    public static int minNumberInRotateArray(int [] array) {
        int start = 0;
        int stop = array.length-1;
        int middle;

        if (array==null || array.length==0)return -100;
        if (array.length == 1)return array[0];
        if (array.length == 2)return less(array,0,1);

        if (array[0] < array[array.length-1])return array[0];

        while (start <= stop)
        {
            middle = start+(stop-start)/2;

            if (start+1 == stop)
            {
                System.out.println(start+" "+stop);
                return less(array,start,stop);
            }
            if (array[start] < array[middle])
            {
                start = middle;
            }else if (array[start] > array[middle]){
                stop = middle;
            }else {
                if (array[middle] > array[stop]){
                    start++;
                }else {
                    stop--;
                }
            }

        }
        return -1;
    }

    public static int less(int[] array,int start,int stop){
        int i = Integer.MAX_VALUE;
        for (int j = start; j <= stop; j++) {
            if (i>=array[j]){
                i = array[j];
            }
        }
        return i;
    }
}
